﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace _970_powerful_integers
{
    class Program
    {
        static void Main (string[] args)
        {
            Solution n = new Solution ();
            List<int> nums = n.PowerfulIntegers1 (2, 0, 10);
            for (int i = 0;i < nums.Count;i++)
            {
                Console.Write (nums[i] + " ");
            }
        }
    }

    public class Solution
    {
        public List<int> PowerfulIntegers (int x, int y, int bound)
        {
            List<int> arr = new List<int> ();

            int count = 0;
            
            if (x != 1 && y != 1 && x != 0 && y != 0)
            {
                count = Order (x, y, bound);

                for (int i = 0;i <= count;i++)
                {
                    for (int j = 0;j <= count;j++)
                    {
                        int num = (int)Math.Pow (x, i) + (int)Math.Pow (y, j);
                        if (!arr.Contains (num) && num > 0 && num <= bound) arr.Add (num);
                        num = (int)Math.Pow (x, j) + (int)Math.Pow (y, i);
                        if (!arr.Contains (num) && num > 0 && num <= bound) arr.Add (num);
                    }
                }
            }
            else if (y == 1 || y == 0)
            {
                
                for (int i = 0;i < bound;i++)
                {
                    int num = (int)Math.Pow (x, i) + y;
                    if (!arr.Contains (num) && num > 0 && num <= bound) arr.Add (num);
                }
            }
            else if (x == 1 || x == 0)
            {
                for (int i = 0;i < bound;i++)
                {
                    int num = (int)Math.Pow (y, i) + x;
                    if (!arr.Contains (num) && num > 0 && num <= bound) arr.Add (num);
                }
            }

            


            return arr;
        }

        public int Order (int x, int y, int bound)
        {
            int numx = 1, numy = 2;
            while (x <= bound)
            {
                numx++;
                x *= x;
            }
            while (y <= bound)
            {
                numy++;
                y *= y;
            }
            return Math.Max (numx, numy);
        }


        public List<int> PowerfulIntegers1 (int x, int y, int bound)
        {
            HashSet<int> h = new HashSet<int> ();
            for (int i = 0;;i++)
            {
                int j = 0;
                for (j = 0;;j++)
                {
                    int res = (int)(Math.Pow (x, i) + Math.Pow (y, j));
                    if (res <= bound) h.Add (res);
                    else break;
                    if ((y == 1 || y == 0) && j > 0) break;
                }
                if (j == 0 || x == 1 ) break;
            }
            return h.ToList ();
        }
    }
}
